A cache in a central processing unit is a data storage structure that is used by the central processing unit of a computer to reduce the average time that it takes to access memory. It is a memory which stores copies of data that is located in the most frequently used main memory locations. Moreover, cache memory is memory that is smaller and that may be accessed more quickly than main memory. There are several different types of caches. These include physically indexed physically tagged (PIPT), virtually indexed virtually tagged (VIVT) and virtually indexed physically tagged (VIPT).
VIPT caches are commonly used in modern processing applications. These caches use a virtual address (VA) for the index (which identifies a unique location in cache memory) and a physical address in the tag (which contains the main memory index of the datum that has been cached) that are associated with cache lines. Using this type of cache, a cache line can be identified in parallel with translation lookaside buffer (TLB) translation as is illustrated in FIG. 1. Referring to FIG. 1, a VIPT cache starts a tag read using virtual address bits 101 (e.g., un-translated virtual address bits) to index into the cache 103, while Memory Management Unit (MMU) 105 translates some of the higher order bits of the virtual address, to physical address bits 107. Physical address bits 107 are thereafter compared with the tag value of the VIPT cache that is associated with the cache line. Thus, VIPT caches are able to hide their access time, by overlapping their tag read process with the MMU translation process.
Consider a 64 KB, 8 way associative level 1 VIPT cache. Moreover, assume a minimum MMU page size of 4 KB, 32b long virtual address (VA) and 40b long physical address (PA). Based on the processes described above, the VIPT cache uses VA[12:6] (bits [12:6] of the virtual address) to index into a Tag SRAM (not shown) to generate TagPA[39:12] (the physical address associated with the un-translated virtual address presented to the Tag SRAM) from all 8 ways. While the VIPT cache is busy accessing it's Tag SRAM, the MMU translates VA[31:12] (bit twelve) to produce MMU PA[39:12] (the physical address that is generated from the translation). MMU PA[39:12] is compared against TagPA[39:12] to generate TagHit[7:0] which identifies the way among the 8 ways of the VIPT cache that has the cache line. Above, VA[12] is used to index into the Tag SRAM, while VA[12] goes through translation to generate a PA[12]. Indexing the cache with a virtual address bit that also gets translated into a physical address, can result in synonyms. Consider the following result:
VA0[31:13]=0x0, VA0[12]=0x0, VA0[11:0]=0x0→(Translation)→PA[39:0]=0x0
VA1 [31:13]=0x1, VA1[12]=0x1, VA1[11:0]=0x0→(Translation)→PA[39:0]=0x0
Above, VA0 and VA1, that differ in their 12th bit, when translated by the MMU, produce the same PA[39:0]. When VA0 accesses the VIPT cache using VA[12:6] (VA[12:6]=0000000), it accesses index 0 of the Tag SRAM (not shown). Moreover, when VA1 accesses the VIPT cache using VA[12:6] (VA[12:6]=0000001), it accesses index 64 of the Tag SRAM. Thus, the same physical address is associated with VA1 and VA2 and resides in both index 0 and index 64 of the VIPT cache. The two virtual addresses, VA1 and VA2 that map to the same physical address of main memory are referred to as “synonyms”. The same physical address being associated with two (or more) entries in the VIPT cache is known as “aliasing.”
Aliasing arises when a size of “a way” of a VIPT cache exceeds the smallest memory page size. Unaddressed, aliasing can result in data inconsistencies. A conventional method of addressing aliasing, when a level 1 or L1 cache is included in a level 2 or L2 cache (a copy of the entire contents of the L1 cache is maintained in the L2 cache), is to store synonym-VA bits (in the above example VA[12]) in L2 cache's tag. A drawback of this method is that a storage bit (e.g., VA[12]) is required for every L2 tag index and an additional bit is required to identify each synonym. Thus, the conventional methodology is deficient as it causes a two dimensional growth in storage in the L2 cache that corresponds to increases in the size of the L2 cache and in the number of synonyms that are contained therein. In addition, in conventional systems, when data associated with a physical address that is mapped to virtual address synonyms is updated, only one location in cache may be updated. In order to avoid data inconsistencies that can result from such incomplete updates, many conventional systems execute a time consuming search of the contents of the cache to ensure the invalidation of all virtual address synonyms that are related to the physical address that is updated. Accordingly, because of their burdensome data storage and cache searching operations, conventional approaches to managing synonyms have significant shortcomings.